package com.yvon.service.demo.algorithm.offer;

/**
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9814-%20I.%20%E5%89%AA%E7%BB%B3%E5%AD%90/README
 */
public class P14_1 {

    public static void main(String[] args) {
        Solution solution = new P14_1().new Solution();
        int i = solution.cuttingRope(11);
        System.out.println(i);
    }

    /**
     * 长度为n的绳子，请把绳子剪成整数长度的m段，长度为3的段数越多（切割越接近自然底数(约等于2.7)乘积越大！），最后的乘积越大。
     * 所以尽可能的划分更多的3，最多能够划分长度为3的块数：n/3。剩下的长度根据n%3划分为三种情况：
     * 0：全部切割为长度为三。
     * 1：减少一块3,和剩下的1凑成4，然后分成两块各为2。
     * 2：最后一块就是2。
     */
    class Solution {
        public int cuttingRope(int n) {
            if (n < 4) {
                return n - 1;
            }
            // n能被3整除为num等份
            int num = n / 3;
            // 余数为rest
            int rest = n % 3;
            if (rest == 0) {
                return (int) Math.pow(3, num);
            }
            else if (rest == 1) {
                return (int) Math.pow(3, num-1) * 4;
            }else {
                return (int) Math.pow(3, num) * 2;
            }
        }

        public int cuttingRope1(int n) {
            if (n < 4) {
                return n - 1;
            }
            int ans = 1;
            // 当最后的余数为2,3,4时，跳出循环
            while (n > 4) {
                ans *= 3;
                n -= 3;
            }
            // 将剩余的余数乘上
            ans *= n;
            return ans;
        }
    }
}
